package com.loriot.common.combination_sum_iv_377;

import java.util.ArrayList;
import java.util.List;

public class Main {
    class Solution {
        int count = 0;
        List<Integer> path = new ArrayList();
        public int combinationSum4(int[] nums, int target) {
            backTracking(0, target, nums);
            return count;
        }
        void backTracking(int start, int target, int[] nums){
            System.out.println(start+" "+target);
            if(target==0){
                System.out.println(path);
                count++;
            }
            if(target<=0)return ;
            for(int i=start;i<nums.length;i++){
                path.add(nums[start]);
                backTracking(i, target-nums[i],nums);
                path.remove(path.size()-1);
            }
        }
    }
    class Solution2 {
        int count = 0;
        List<Integer> path = new ArrayList();
        public int combinationSum4(int[] nums, int target) {
            int[] dp = new int[target+1];
            // 目标值是0的组合数，必为1，就是为空的时候
            dp[0] = 1;
            // i是目标值
            for(int i=1;i<=target;i++){
                for(int j=0;j<nums.length;j++){
                    // 如果遍历的值大于目标值
                    if(nums[j]>i)continue;
                    dp[i] += dp[i-nums[j]];
                }
            }
            return dp[target];
        }

    }
}
